A programmable logic device (PLD) is designed to be user-programmable so that users may implement logic designs of their choices. Programmable logic circuits of a PLD comprise gates which are configurable by a user of the circuit to implement a circuit design of the user. One type of PLD is the Complex Programmable Logic Device, or CPLD. A CPLD includes two or more “function blocks” connected together and to input/output (I/O) resources by an interconnect switch matrix. Each function block of the CPLD includes a two-level AND/OR structure similar to that used in a Programmable Logic Array (PLA) or a Programmable Array Logic (PAL) device. In some CPLDs, configuration data is stored on-chip in non-volatile memory, then downloaded to volatile memory as part of an initial configuration sequence.
Another type of PLD is a field programmable gate array (FPGA). In a typical FPGA, an array of configurable logic blocks (CLBs) is coupled to programmable input/output blocks (IOBs). The CLBs and IOBs are interconnected by a hierarchy of programmable routing resources. These CLBs, IOBs, and programmable routing resources are customized by loading a configuration bitstream, typically from off-chip memory, into configuration memory cells of the FPGA. For both of these types of programmable logic devices, the functionality of the device is controlled by configuration data bits of a configuration bitstream provided to the device for that purpose. The configuration data bits may be stored in volatile memory (e.g., static memory cells, as in FPGAs and some CPLDs), in non-volatile memory (e.g., FLASH memory, as in some CPLDs), or in any other type of memory cell.
PLDs also have different “modes” depending on the operations being performed on them. A specific protocol allows a programmable logic device to enter into the appropriate mode. Typical PLDs have internal blocks of configuration memory which specify how each of the programmable cells will emulate the user's logic. During a “program” mode, a configuration bitstream is provided to non-volatile memory, such as a read-only memory (ROM) (e.g. a programmable ROM (PROM), an erasable PROM (EPROM), an electrically erasable PROM (EEPROM)) either external or internal to the programmable logic device. Each address is typically accessed by specifying its row and column addresses. During system power up of a “startup” mode, the configuration bits are successively loaded from the non-volatile memory into static random access memory (SRAM) configuration latches of a configuration logic block. Configuration bitstreams are typically loaded in frames, where the frames are no larger than the depth of a memory. For example, the frame would be no larger than N for an N×N memory array. At the end of this start-up phase, the PLD is now specialized to the user's design, and the PLD enters into “user” mode as part of its normal operation.
However, for the PLD to function properly, it is necessary that the data loaded into a memory is not corrupted. Accordingly, data is often read back and checked against known data to check for an error. Error checking may include both error detection and correction, or error detection without error correction. Because it is necessary to know the location of an error to correct the error, error detection techniques which only indicate the presence of errors (such as the number of errors) but not the location of errors cannot be used alone to correct errors. One conventional technique for detecting and in some cases correcting an error in a frame of data is a single error correction-double error detection (“SECDED”) decoding technique. SECDED codes for encoding information, which are also known as “distance-4 Hamming codes,” may be used for decoding a string of bits, where error checking or parity bits have been added to a set of data bits. A parity bit is any bit associated with one or more data bits for error checking a transmission of such data bits. Conventionally, parity bits are transmitted with data bits. For SECDED decoding, if any one bit, including data and parity bits, of a transmission is in error, the error can be detected and corrected; and if any two bits, including data bits, parity bits, or any combination of data and parity bits, of a transmission are in error, the error can be detected although it cannot be corrected.
In particular, when data is read back from the memory device, stored parity bits are compared with a newly created set of parity bits from the read data. The result of this comparison, called the syndrome, will indicate the incorrect bit position in a single data error. The syndrome is created upon a memory read and provides the ability to correct single bit errors. SECDED for N bits of data requires K parity bits to be stored with the data where N≦2K−1−K. If the bits are numbered in sequence, those bit positions that represent powers of two are dedicated to parity bits. One additional parity bit detects double errors that are not correctable. This extra parity bit is an overall parity bit and is comprised by XOR-ing all the data bits and parity bits. While SECDED has been used in conventional devices to detect and possibly correct errors in the vertical direction of array, the location of multiple errors cannot be detected, and the presence of more that two errors in a frame will not be detected.
According to another error detection technique called a cyclic redundancy check (CRC), the number of errors even greater than two can be identified. CRC is used to protect blocks of data or frames. In performing a CRC, a transmitter apends an extra n-bit sequence called a Frame Check Sequence (FCS) to every frame. The FCS holds redundant information about the frame that helps the transmitter detect errors in the frame. However, a CRC provides no indication as to the location of the errors. While the detection of the number of errors provides value in determining whether errors exist, the number of errors alone generally provides little help in correcting errors. Further, as device dimensions are decreasing, the number of errors in a memory array is increasing. For example, a cosmic ray, which is generally less than a few microns, may upset as many as three memory cells in devices currently manufactured to small dimensions.
Certain applications of programmable logic devices, such as military, aerospace, and high-reliability communications, require detection of errors even when the likelihood of such an occurrence is extremely low. Furthermore, applications running in redundant systems require fast indication of a single event upset (SEU) in order to minimize the impact upon operation. In many cases, fast correction with minimal impact upon operation is also required. Even the rare SEU must be detected for some high-reliability systems so that appropriate system measures can be taken to ensure very high uptime. In certain applications, automatic correction of errors may also be a significant advantage. When processing real-time streaming data such as a video signal, for example, automatic correction of errors allows operation to continue without the need for a system reset. At a minimum, error correction allows much faster system recovery time because the FPGA does not have to be completely reconfigured, possibly causing many seconds of system downtime. With the FPGA configuration automatically corrected, a logical reset to a known system state is all that would normally be required after an error correction event.
Accordingly, there is a need for an improved method of correcting errors stored in a memory.